package 哈希表;

import java.util.HashMap;

/**
 * 空间换时间
 *
 * @Author Weton Li
 * @Date 2021/2/27 12:43
 */
public class 一_求两数之和 {

    public static int[] soulution(int[] nums, int target) {

        HashMap<Integer, Integer> map = new HashMap<>();

        int n = nums.length;
        // 1.遍历数组元素保存在hashmap中

        // 2.遍历数组通过目标值找出它的匹配值
        for (int i = 0; i < n; i++) {
            int another = target - nums[i]; // 我的伴侣
            if (map.containsKey(another)) {
                Integer index2 = map.get(another); // 伴侣索引
                return new int[]{index2, i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("无法解决");
    }


    public static void main(String[] args) {
        int[] nums = {2, 7, 8, 11}; // 返回0,1
        int[] nums1 = {3,2,4}; // 返回0,1
        int target = 9;
        int target1 = 6;

//        int []input = new int[1000000];
//        for (int i = 0; i < input.length; i++) {
//            input[i] = input.length-i;
//        }
//        int targetN = 99999;
//        long startTime = System.currentTimeMillis();

        int[] soulution = soulution(nums, target);
        int[] res = method(nums1, target1);
//        int[] soulution = soulution(input, targetN);
//        for (int i : soulution) {
//            System.out.print(i+",");
//        }
//        long endTime = System.currentTimeMillis();
//
//        System.out.println("耗时"+(endTime-startTime)+"ms");
        for (int i : res) {
            System.out.print(i + "\t");
        }

    }

    public static int[] method1(int[] nums, int target) {
        int n = nums.length;

        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{-1};
    }

    public static int[] method2(int[] nums, int target) {
        int n = nums.length;

        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(i, nums[i]); // k:当前值的索引位置，v:数组值
        }


        /*
        5,2,7,11
        0:5
        1:2
        2:7
        3:11
        找9-2=7找到即可
         */

        for (int i = 0; i < n; i++) {
            int thatNum = target - nums[i]; // 9-5=4
            // 这里从每轮i的下一个数开始判断，防止3,2,4 target=6情况下6-3=3，若仍从第一个数遍历，则返回0,0。
            for (int j = i+1; j < n; j++) {
                if (map.get(j) == thatNum) {
                    return new int[]{i,j};
                }
            }
        }
        return new int[]{0,0};
    }

    public static int[] method(int[] nums,int target){
        int n = nums.length;
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < n; i++) {

            int thatNum = target-nums[i];
            if (map.containsKey(thatNum)) {
                return new int[]{map.get(thatNum),i};
            }else {
                map.put(nums[i], i);
            }
        }
        return new int[]{0,0};
    }


}
